ass Solution {
public:
    bool isValid(string s) 
    {
        // 因为我们使用栈的话必须要保证匹配 
        // 如果是左边的几种类型我们才入栈
        // 如果是右边的我们就往栈里面匹配 
        // 如果最后全部匹配完了 栈为空则我们返回true 
        // 如果不为空 或者最后字符串遍历完毕了栈中还有数据则为假

        stack<char> stack;
        for (int i = 0; i < s.size() ; i++)
        {
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                stack.push(s[i]);
            }
            else
            {
                if (stack.empty())
                {
                    return false;
                }
                if (s[i] == ')')
                {
                    if (stack.top() != '(')
                    {
                        return false;
                    }
                    else
                    {
                        if (stack.empty())
                        {
                            return false;
                        }
                        stack.pop();
                    }
                }
                else if (s[i] == ']')
                {
                    if (stack.top()!='[')
                    {
                        return false;
                    }
                    else
                    {
                        stack.pop();
                    }
                }
                else
                {
                    if (stack.top() != '{')
                    {
                        return false;
                    }
                    else
                    {
                        stack.pop();
                    }
                }
            }
        }                           

        if (stack.empty())
        {
            return true;
        }         
        else
        {
            return false;
        }
    }
};
